///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<Integer>();
//        if (root == null) {
//            return res;
//        }
//
//        Deque<TreeNode> stack = new LinkedList<TreeNode>();
//        TreeNode node = root;
//        while (!stack.isEmpty() || node != null) {
//            while (node != null) {
//                res.add(node.val);
//                stack.push(node);
//                node = node.left;
//            }
//            node = stack.pop();
//            node = node.right;
//        }
//        return res;
//    }
//}

public static void preOrderIteration(TreeNode head) {
        if (head == null) {
        return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.value + " ");
        if (node.right != null) {
        stack.push(node.right);
        }
        if (node.left != null) {
        stack.push(node.left);
        }
        }
        }
